/**
 * 二叉树的还原
 *
 *      A
 *    /   \
 *   B     C
 *  / \   / \
 * D   E F   G
 *
 * 前序 ABDECFG
 * 中序 DBEAFCG
 * 后序 DEBFGCA
 */

class TreeNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

let before = ['A', 'B', 'D', 'E', 'C', 'F', 'G'];
let mid = ['D', 'B', 'E', 'A', 'F', 'C', 'G'];
let after = ['D', 'E', 'B', 'F', 'G', 'C', 'A'];

/**
 * 根据前序中序还原二叉树
 * @param before 前序遍历
 * @param mid 中序遍历
 * @returns {TreeNode|null}
 */
function beforeCreateTree(before, mid) {
  if (before == null || mid == null || before.length == 0 || mid.length == 0 || before.length != mid.length) return null;
  let root = new TreeNode(before[0]);
  let index = mid.indexOf(before[0]);
  root.left = createTree(before.slice(1, index + 1), mid.slice(0, index));
  root.right = createTree(before.slice(index + 1), mid.slice(index + 1));
  return root;
}

let beforeTree = beforeCreateTree(before, mid);
console.log("▶『beforeCreateTree』", beforeTree);

/**
 * 根据后序中序还原二叉树
 * @param after 后序遍历
 * @param mid 中序遍历
 * @returns {TreeNode|null}
 */
function afterCreateTree(after, mid) {
  if (after == null || mid == null || after.length == 0 || mid.length == 0 || after.length != mid.length) return null;
  let root = new TreeNode(after[after.length - 1]);
  let index = mid.indexOf(before[0]);
  root.left = createTree(after.slice(0, index), mid.slice(0, index));
  root.right = createTree(after.slice(index), mid.slice(index));
  return root;
}

let afterTree = afterCreateTree(after, mid);
console.log("▶『afterCreateTree』", afterTree);
